// // 2、将两个非递减的有序表合并为一个非递增的有序表。
// // 要求结果链表仍然使用原来两个链表的存储空间，
// // 不占用另外的存储空间。表中允许有重复的数据。
// #include <stdio.h>
// #include <stdlib.h>
// //节点结构
// typedef struct LinkNode {
//     int data;
//     struct LinkNode* next;
// }LinkNode;
// //链表结构
// typedef struct LinkList {
//     LinkNode* head;
// }LinkList;
// //链表初始化
// LinkList* LinkInit() {
//     LinkList* list=(LinkList*)malloc(sizeof(LinkList));
//     list->head=(LinkNode*)malloc(sizeof(LinkNode));
//     list->head->next=NULL;
//     return list;
// }
//
// // 插入节点到链表尾部
// void LinkInsert(LinkList* list,int data) {
//     LinkNode* newNode=(LinkNode*)malloc(sizeof(LinkNode));
//     if(newNode==NULL) {
//         perror("malloc");
//     }
//     newNode->data=data;
//     newNode->next=NULL;
//     LinkNode* current=list->head;
//     while (current->next!=NULL) {
//         current=current->next;
//     }
//     current->next=newNode;
// }
// //打印链表
// void printLinkList(LinkList* list) {
//     LinkNode* current=list->head->next;
//     while(current!=NULL) {
//         printf("%d ",current->data);
//         current=current->next;
//     }
//     printf("\n");
// }
// //合并
// LinkList* LinkMerge(LinkList* L1,LinkList* L2) {
//     LinkList* L3=LinkInit();
//     L3->head->next=NULL;
//     LinkNode* l1=L1->head->next;
//     LinkNode* l2=L2->head->next;
//     LinkNode* l3=L3->head;
//     while (l1!=NULL&&l2!=NULL) {
//         if(l1->data<l2->data) {
//             l3->next=l1;
//             l1=l1->next;
//         }else {
//             l3->next=l2;
//             l2=l2->next;
//         }
//         l3=l3->next;
//     }
//     while(l1!=NULL) {
//         LinkInsert(L3,l1->data);
//         l1=l1->next;
//     }while(l2!=NULL) {
//         LinkInsert(L3,l2->data);
//         l2=l2->next;
//     }
//     free(L1->head);
//     free(L2->head);
//     free(L2);
//     free(L1);
//     // 反转L3链表
//     LinkNode* prev = NULL; // 初始化前一个节点为NULL
//     LinkNode* current = L3->head->next; // 初始化当前节点为链表的第一个有效节点
//     while (current != NULL) { // 遍历链表，直到当前节点为NULL
//         LinkNode* next = current->next; // 保存当前节点的下一个节点
//         current->next = prev; // 将当前节点的next指针指向前一个节点，实现反转
//         prev = current; // 更新前一个节点为当前节点
//         current = next; // 更新当前节点为下一个节点
//     }
//     L3->head->next = prev; // 最后，将头节点的next指针指向新的头节点（即prev）
//     return L3;
// }
// int main() {
//     LinkList* L1=LinkInit();
//     LinkList* L2=LinkInit();
//     LinkInsert(L1,1);
//     LinkInsert(L1,3);
//     LinkInsert(L1,3);
//     LinkInsert(L1,5);
//     LinkInsert(L1,7);
//     LinkInsert(L1,9);
//     LinkInsert(L1,9);
//     LinkInsert(L2,2);
//     LinkInsert(L2,4);
//     LinkInsert(L2,4);
//     LinkInsert(L2,6);
//     LinkInsert(L2,8);
//     LinkInsert(L2,8);
//     LinkInsert(L2,10);
//     printf("L1:");
//     printLinkList(L1);
//     printf("\n");
//     printf("L2:");
//     printLinkList(L2);
//     printf("\n");
//     LinkList* L3=LinkInit();
//     L3=LinkMerge(L1,L2);
//     printf("L3:");
//     printLinkList(L3);
//     free(L3);
//     return 0;
// }
// // L3反转的详细步骤如下↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
// //-------------------------------------------------
// // 详细步骤
// // 初始化指针：
// // prev初始化为NULL，表示前一个节点。
// // current初始化为L3->head->next，即链表的第一个有效节点。
// // 遍历链表：
// // 使用while循环遍历链表，直到current为NULL。
// // 在每次循环中，执行以下步骤：
// // LinkNode* next = current->next;：保存当前节点的下一个节点，以便在反转指针后能够继续遍历链表。
// // current->next = prev;：将当前节点的next指针指向前一个节点，实现节点的反转。
// // prev = current;：更新prev为当前节点，为下一次循环做准备。
// // current = next;：更新current为下一个节点，继续遍历链表。
// // 更新头节点：
// // 循环结束后，prev将指向新的头节点（即原链表的最后一个节点）。
// // L3->head->next = prev;：将头节点的next指针指向新的头节点，完成链表的反转。
// // 示例
// // 假设链表的初始状态为：1 -> 2 -> 3 -> 4 -> 5 -> NULL
// // 初始化：
// // prev = NULL
// // current = 1
// // 第一次循环：
// // next = 2
// // 1->next = NULL（1的next指针指向前一个节点NULL）
// // prev = 1
// // current = 2
// // 第二次循环：
// // next = 3
// // 2->next = 1（2的next指针指向前一个节点1）
// // prev = 2
// // current = 3
// // 第三次循环：
// // next = 4
// // 3->next = 2（3的next指针指向前一个节点2）
// // prev = 3
// // current = 4
// // 第四次循环：
// // next = 5
// // 4->next = 3（4的next指针指向前一个节点3）
// // prev = 4
// // current = 5
// // 第五次循环：
// // next = NULL
// // 5->next = 4（5的next指针指向前一个节点4）
// // prev = 5
// // current = NULL
// // 更新头节点：
// // L3->head->next = 5（将头节点的next指针指向新的头节点5）
// // 最终，链表的状态变为：5 -> 4 -> 3 -> 2 -> 1 -> NULL